Question? Leave a message!

Difference between stacks and queues

how to use stacks and queues in java and stack and queue exam questions
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
4.3 Stacks and Queues Introduction to Programming in Java: An Interdisciplinary Approach · Robert Sedgewick and Kevin Wayne · Copyright © 2002–2010 · 6/26/10 8:10 AM Data Types and Data Structures Data types.   Set of values.   Set of operations on those values.   Some are built in to Java: int, double, char, . . .   Most are not: Complex, Picture, Stack, Queue, Graph, … this lecture Data structures.   Represent data or relationships among data.   Some are built into Java: arrays, String,…   Most are not: linked list, circular list, tree, sparse array, graph, . . . this lecture TSP assignment next lecture 2 Collections Fundamental data types.   Set of operations (add, remove, test if empty) on generic data.   Intent is clear when we insert.   Which item do we remove? this lecture Stack. LIFO = last in first out   Remove the item most recently added.   Ex: cafeteria trays, Web surfing. Queue. FIFO = first in, first out   Remove the item least recently added.   Ex: Registrar's line. next lecture Symbol table.   Remove the item with a given key.   Ex: Phone book. 3 Stacks 4 Stack API push pop public class Reverse public static void main(String args) StackOfStrings stack = new StackOfStrings(); while (StdIn.isEmpty()) stack.push(StdIn.readString()); while (stack.isEmpty()) StdOut.println(stack.pop()); 5 Stack Client Example 1: Reverse public class Reverse public static void main(String args) StackOfStrings stack = new StackOfStrings(); while (StdIn.isEmpty()) String s = StdIn.readString(); stack.push(s); while (stack.isEmpty()) String s = stack.pop (); StdOut.println(s); % more tiny.txt it was the best of times % java Reverse tiny.txt times of best the was it stack contents when standard input is empty 6 Stack Client Example 2: Test Client public static void main(String args) StackOfStrings stack = new StackOfStrings(); while (StdIn.isEmpty()) String s = StdIn.readString(); if (s.equals("-")) StdOut.println(stack.pop()); else stack.push(s); % more test.txt to be or not to – be - - that - - - is % java StackOfStrings test.txt to be not that or be stack contents just before first pop operation 7 Stack: Array Implementation how big to make array? stay tuned Array implementation of a stack.   Use array a to store N items on stack.   push() add new item at aN. stack and array contents th   pop() remove item from aN-1. after 4 push operation to be or not a 0 1 2 3 4 5 6 7 8 9 N public class ArrayStackOfStrings private String a; temporary solution: make client provide capacity private int N = 0; public ArrayStackOfStrings(int max) a = new Stringmax; public boolean isEmpty() return (N == 0); public void push(String item) aN++ = item; public String pop() return aN; 8 Array Stack: Test Client Trace push pop 9 Array Stack: Performance Running time. Push and pop take constant time. Memory. Proportional to client-supplied capacity, not number of items. Problem.   API does not call for capacity (bad to change API).   Client might use multiple stacks.   Client might not know what capacity to use. Challenge. Stack implementation where size is not fixed ahead of time. 10 Linked Lists 11 Sequential vs. Linked Allocation Sequential allocation. Put object one after another.   TOY: consecutive memory cells.   Java: array of objects. Linked allocation. Include in each object a link to the next one.   TOY: link is memory address of next object. addr value addr value   Java: link is reference to next object. C0 "Alice" C0 "Carol" C1 "Bob" C1 null C2 "Carol" C2 - C3 - C3 - th get i element Key distinctions. C4 - C4 "Alice" C5 - C5 CA   Array: random access, fixed size. C6 - C6 -   Linked list: sequential access, variable size. C7 - C7 - C8 - C8 - get next element C9 - C9 - CA - CA "Bob" CB - CB C0 linked list array 12 Linked Lists Linked list.   A recursive data structure.   An item plus a pointer to another linked list (or empty list).   Unwind recursion: linked list is a sequence of items. public class Node Node data type. private String item;   A reference to a String. private Node next;   A reference to another Node. first Alice Bob Carol null item next special pointer value null terminates list 15 Building a Linked List addr Value Node third = new Node(); C0 "Carol" third.item = "Carol"; = null; C1 null C2 - Node second = new Node(); second.item = "Bob"; C3 - = third; first C4 C4 "Alice" Node first = new Node(); second CA C5 CA first.item = "Alice"; third C0 C6 - = second; C7 - C8 - C9 - CA "Bob" CB C0 CC - first second third CD - CE - Alice Bob Carol null CF - item next main memory 16 Stack Push: Linked List Implementation first best the was it first second best the was it Node second = first; second first best the was it first = new Node(); second first first.item = "of"; of best the was it = second; 17 Stack Pop: Linked List Implementation "of" first of best the was it String item = first.item; first of best the was it first =; garbage-collected first best the was it return item; 18 Stack: Linked List Implementation public class LinkedStackOfStrings private Node first = null; private class Node private String item; private Node next; "inner class" public boolean isEmpty() return first == null; public void push(String item) Node second = first; first = new Node(); first.item = item; stack and linked list contents = second; th after 4 push operation public String pop() String item = first.item; first =; return item; 19 Linked List Stack: Test Client Trace push pop 20 Linked List Stack: Performance Running time. Push and pop take constant time. Memory. Proportional to number of items in stack. 21 Stack Data Structures: Tradeoffs Two data structures to implement Stack data type. Array.   Every push/pop operation take constant time.   But… must fix maximum capacity of stack ahead of time. Linked list.   Every push/pop operation takes constant time.   But… uses extra space and time to deal with references. 22