Revision – Stack and Queue

Data Structures & Algorithms Analysis

1
Lecture Outline
 Stack
 Using an array
 Using linked list
 Queue
 Using linked list

2
Learning Objective
 To elaborate the concepts of stack and queue,
 To differentiate and apply the concept of stack and queue in
programming, and
 To implement the operation of inserting and removing in
programming using stack and queue.

3
Stack
 The addition and deletion are made to one end, the top
 The item most recently added is always on the top
 Most commonly used in computer science world, especially
by many algorithms (E.g.: compiler, run-time environment)
 Analogy:

4
Stack
 More restrictive data structure because client can access
only a single element at topmost of the stack.
 A stack is a data structure in which only the top element
can be accessed.
 Storing a data item in a stack is called pushing it onto the
stack
 Removing a value from a stack is called popping the stack
 A stack behaves like a linked list in which all insertions and
deletions are performed at the list head.
 Pointer that point to the first node is called “top”
 Concepts : Last In First Out (LIFO)

5
Specifications of the ADT Stack

A stack of strings after (a) push adds Jim;

(b) push adds Jess; (c) push adds Jill; (d) push adds Jane; (e) push adds
Joe; (f) pop retrieves and removes Joe; (g) pop retrieves and removes
Jane
6
Stack using an array

 In array, pointer “top” is assumed as a counter.

 Counter “top” must be initialized with –1.
 Adding data, counter must be increase by 1
 Removing data, counter must be decrease by 1

7
 Stack using an array
  3   push(1)   3  

  2     2  

  1     1  

0   top 0 1

top = -1
push(3) push(8) pop() push(7)
  3               3  

  2   top 8       top 2 7

top 1 3   3 top 3     1 3

  0 1   1   1     0 1

8
Stack using linked list
 Before creating a stack, pointer “top” must be initialized with
“null”.
 It means the stack is empty

9
Stack using linked list
 When using a chain of linked nodes to implement a stack
 The first node should reference the stack's top

A chain of linked nodes that implements a stack.

10
A Linked Implementation

(a) A new node that references the top of the stack; (b) the new node is now
at the top of the stack.

11
Specifications of the ADT Stack

Data Field Attribute

Node top A reference to the top of the stack
Methods Behavior
void push(Object) Place the argument at the top of the stack
Object pop() Retrieve and remove object at the top of the stack
Object peek() Retrieve object at the top of stack without removal
boolean isEmpty() Returns true if stack is empty
; false if not empty.

In Java API, class [Link] implement a stack

ADT

12
Class StackList
public class StackList {
// Data fields
private Node top; // reference to
// top of stack
// Methods
public StackList() {
top = null; // new stack is empty
}
/* push - pushes an item onto a stack
* postcondition: item is at the top of the stack
*/
public void push(Object item) {
//Allocate a new node, store item in it, and
// link it to old top of stack.
top = new Node(item, top);
}

/* postcondition: Returns item at top of stack and

* removes it. Throws an exception if stack is empty.
*/
public Object pop() {
Object item = peek(); // Retrieve item at top
//Remove old top of stack
top = [Link](); // Link top to second element
13 return item; // Return data at old top
}
Class StackList, cont...

/* peek - retrieves an item from a stack

* postcondition: Returns item at top of stack without
* removing it. Throws an exception if stack is empty.
*/
public Object peek() {
if (isEmpty())
throw new NullPointerException();
return [Link](); //return top item
}

/* isEmpty - tests whether a stack is empty

* postcondition: returns true if stack is empty;
* otherwise, returns false.
*/
public boolean isEmpty() {
return (top == null);
}
} // class StackList

14
 Stack - Removing node

top = [Link]() // top = [Link]

X 2 4 5 7
top

4 5 7
top
remove 2

15
 Stack - Inserting a node

 Algo.
 If list is empty
 Set pointer “top” to new node
 else
 Set pointer “link” of new node to the first node
 Set pointer “top” to the new node
.

top

2
newNode

16
Stack - Inserting a node:empty list
Node newNode = new Node(new Integer(8))
 code
if (top == null)
top = newNode;
else {
[Link](top); // [Link] = top
top = newNode;
}
count++;

top = newNode

X 8
top
newNode
8
top

17
Insert 8
Stack-Inserting a node:non empty list

 code
Node newNode = new Node(new Integer(7))
if (top == null)
top = newNode;
else {
[Link](top); // [Link] = top
top = newNode;
}
count++;

X 8
top
top = newNode [Link] = top
7 X
newNode
7 8
top
18
Insert 7
Queues
 A queue (pronounced “Q”) is a list-like structure in which items are
inserted at one end and removed from the other end
 Elements are removed from the front of the queue and inserted at
the rear of the queue
 Concepts : First-In-First-Out (FIFO) structure.
 A queue can be used to model a line of customers waiting at a
checkout counter or a stream of jobs waiting to be printed by a
printer
 Pointer that point to the first node is called “front”, “head”, “first
node”
 Pointer that point to the last node is called “rear”, “tail”, “last node”

19
Queue

Some everyday queues.

20
 Specifications for the ADT Queue

Queue of strings after (a) enqueue adds Jim;

(b) Jess; (c) Jill; (d) Jane; (e) Joe; (f) dequeue retrieves, removes
Jim; (g) enqueue adds Jerry; (h) dequeue retrieves, removes
21
Jess.
Using a Queue to Simulate a Waiting Line

A line, or queue of people.

22
 Example of Queue (FIFO)
1st Operation: enqueue(A); enqueue(B); enqueue (C);

Queue g1

A B C

front rear

2nd Operation: dequeue ();dequeue ();

front rear

3rd Operation: enqueue (D); enqueue (E);

C D E

23 front rear
Queue using linked list

 Before creating a list,

 pointer “rear” and “front” must be initialized with “null”.
 It means the list is empty
 when inserting nodes, pointer “rear” must be pointed to the
last node
 And pointer “front” must be pointed to the first node

24
Queue (a), after insertion (b), after removal(c)

25
 Queue - Removing a node

 Algo.
 If queue is empty
 Return error message
 Else
 If queue contain only one node
 Set pointer “front” and “rear” into null
 else
 Set pointer “front” to second node

26
 Queue - Removing node

front = [Link]() // front = front .link

X 2 4 5 7
front

rear remove 2

rear

4 5 7
front

27
Queue - Inserting a node

 Algo.
 If queue is empty
 Set pointer “front” and “rear” to new node
 else
 Set pointer “link” of rear to the new node
 Set pointer “rear” to the new node
.

28
Queue - Inserting a node: empty list

Node newNode = new Node(new Integer(8))

if (front == null)
{
front = newNode;
rear = newNode;
}
else {
[Link](newNode); // [Link] = newNode
rear = newNode;
}
count++;

X
front
10 front
10
X
rear
29
newNode rear
Queue - Inserting a node:non empty list
Node newNode = new Node(new Integer(7))
if (top == null)
{
front = newNode;
rear = newNode;
} else
[Link](newNode); // [Link] = newNode
rear = newNode;
}
count++;

2 4 5 7 X
front
X
8
rear

newNode

2 4 5 7 8
front
30
rear
 Conclusion

Q & A Session

31