Stacks and Queues Abstract Data Types (ADTs) Abstract

Stacks and Queues Abstract Data Types (ADTs)  Abstract

Stacks and Queues Abstract Data Types (ADTs) Abstract Data Type (ADT): A specification of a collection of data and the operations that can be performed on it. Describes what a collection does, not how it does it We don't know exactly how a stack or queue is implemented, and we don't need to. We just need to understand the idea of the collection and what operations it can perform. Stacks usually implemented with arrays Queues often implemented with a linked list Stacks and Queues Some collections are constrained so clients can only use optimized operations stack: retrieves elements in reverse order as added queue: retrieves elements in same order as added

push top pop, peek 3 2 bottom 1 stack dequeue, first front 1

back 2 queu e 3 enqueue Stacks Stack: A collection based on the principle of adding elements and retrieving them in the opposite order. Last-In, First-Out ("LIFO") Elements are stored in order of insertion. We do not think of them as having indexes. Client can only add/remove/examine

the last element added (the "top"). basic stack operations: push: Add an element to the top. pop: Remove the top element. peek: Examine the top element. push pop, peek top 3 2 bottom 1

stac Stacks in Computer Science Programming languages and compilers: method calls are placed onto a stack call=push return=pop compilers use stacks to evaluate expressions Matching up related pairs of things: find out whether a string is a palindrome examine a file to see if its braces { } match convert "infix" expressions to pre/postfix Sophisticated algorithms: searching through a maze with "backtracking" many programs use an "undo stack" of previous operations

Stack Limitations You cannot loop over a stack in the usual way. Stack s = new Stack(); ... for (int i = 0; i < s.size(); i++) { do something with s.get(i); } Instead, pop each element until the stack is empty. // process (and destroy) an entire stack while (!s.isEmpty()) { do something with s.pop(); } What happened to my stack? Suppose we're asked to write a method max that accepts a Stack of Integers and returns the largest Integer in the stack: // Precondition: !s.isEmpty() public static void max(Stack s) {

int maxValue = s.pop(); while (!s.isEmpty()) { int next = s.pop(); maxValue = Math.max(maxValue, next); } return maxValue; } The algorithm is correct, but what is wrong with the code? What happened to my stack? The code destroys the stack in figuring out its answer. To fix this, you must save and restore the stack's contents: public static void max(Stack s) { Stack backup = new Stack(); int maxValue = s.pop(); backup.push(maxValue);

while (!s.isEmpty()) { int next = s.pop(); backup.push(next); maxValue = Math.max(maxValue, next); } while (!backup.isEmpty()) { // restore s.push(backup.pop()); } return maxValue; } Queues Queue: Retrieves elements in the order they were added. First-In, First-Out ("FIFO") Elements are stored in order of insertion but don't have indexes. Client can only add to the end of the queue, and can only examine/remove

the front of the queue. front back dequeue, first Basic queue operations: 1 2 queue enqueue (add): Add an element to the back. dequeue (remove): Remove the front element. first: Examine the front element. 3

enqueue Queues in Computer Science Operating systems: queue of print jobs to send to the printer queue of programs / processes to be run queue of network data packets to send Programming: modeling a line of customers or clients storing a queue of computations to be performed in order Real world examples: people on an escalator or waiting in a line cars at a gas station (or on an assembly line) Using Queues As with stacks, must pull contents out of queue to view them. // process (and destroy) an entire queue

while (!q.isEmpty()) { do something with q.remove(); } To examine each element exactly once. int size = q.size(); for (int i = 0; i < size; i++) { do something with q.remove(); (including possibly re-adding it to the queue) } Why do we need the size variable? Mixing Stacks and Queues We often mix stacks and queues to achieve certain effects. Example: Reverse the order of the elements of a queue. Queue q = new LinkedList(); q.add(1); q.add(2); q.add(3);

// [1, 2, 3] Stack s = new Stack(); while (!q.isEmpty()) { // Q -> S s.push(q.remove()); } while (!s.isEmpty()) { // S -> Q q.add(s.pop()); } System.out.println(q); // [3, 2, 1] Java Stack Class Stack() push(value ) pop()

constructs a new stack with elements of type T places given value on top of stack removes top value from stack and returns it; throws EmptyStackException if stack is empty peek() returns top value from stack without removing it; if stack is Stack throws s = newEmptyStackException Stack(); s.push("a"); empty s.push("b"); size() returns number

of elements in stack s.push("c"); // bottom ["a", "b", "c"] top isEmpty() returns true if stack has no elements System.out.println(s.pop()); // "c" Stack has other methods that are off-limits (not efficient) Java Queue Interface add(value ) remove() places given value at back of queue removes value from front of queue and returns it; throws a NoSuchElementException if queue is

empty peek() returns front value from queue without removing it; returns null if queue is empty size() returns number of elements in queue Queue q = new LinkedList(); isEmpty() q.add(42); returns true if queue has no elements q.add(-3); q.add(17); // front [42, -3, 17] back System.out.println(q.remove()); // 42 IMPORTANT: When constructing a queue, you must use a new LinkedList object instead of a new Queue object. Because Queue is an interface.

Exercises Write a method stutter that accepts a queue of Integers as a parameter and replaces every element of the queue with two copies of that element. [1, 2, 3] becomes [1, 1, 2, 2, 3, 3] Write a method mirror that accepts a queue of Strings as a parameter and appends the queue's contents to itself in reverse order. [a, b, c] becomes [a, b, c, c, b, a]

Recently Viewed Presentations

  • Santolina Level A Master Plan Transportation System Comments

    Santolina Level A Master Plan Transportation System Comments

    Dennis Chavez/Paseo del Volcan 'Loop' alignment may not meet regional transportation network objectives. Interim Long Range Roadway System adopted by the Metropolitan Transportation Board in October of 2013. 118th St. Interchange w/ I-40.
  • Forces in Fluids - cc040.k12.sd.us

    Forces in Fluids - cc040.k12.sd.us

    Forces in Fluids Chapter 13 What is pressure? The result of a force acting over a given area. Pressure = Force/Area What label? N/m2 1 N/m2 is known as a pascal (Pa) Blaise Pascal 1623-1662 French physicist and mathematician Performed...
  • State Board Practical Exam  The entire exam will

    State Board Practical Exam The entire exam will

    Curl Demo and Roller Placement. Complete 1 on-base roller in top center area, 1 no-stem flat pincurl on right side of head and a three-ridge fingerwave (4x2) behind roller. Time:15 minutes. 1 point each. Procedure Criteria: Sanitizes own hands using...
  • The Stone Angel - Hunni ELA 30-1

    The Stone Angel - Hunni ELA 30-1

    The Stone Angel is also a realistic portrayal of life in the prairie towns of western Canada from the late nineteenth century to the Depression of the 1930s and beyond. Laurence went on to write four more books set in...
  • Using the Metric System A. Why do scientists

    Using the Metric System A. Why do scientists

    The distance between dots on a ticker tape represents the object's position change during that time interval. A large distance between dots indicates that the object was moving fast during that time interval. A small distance between dots means the...
  • Chapter 6: Business Organization &amp; Finance

    Chapter 6: Business Organization & Finance

    Primary industrial activity = natural resources (or raw materials) are being harvested. Secondary industrial activity (manufacturing) = processing raw materials into final or semi-processed goods. Tertiary Industry (Service) - Provide services to consumers ( Retail, stores, etc)
  • Screening - Ipb

    Screening - Ipb

    The two-stage screening hardware can be installed new or retrofit in diameters from 40 to 100" (1015 to 2540mm) to scalp up to 70 tons per hour. Available to 3-A, FDA, BISSC and other sanitary standards, the units can be...
  • Statistical Considerations for Studies Involving Mice (et al.)

    Statistical Considerations for Studies Involving Mice (et al.)

    21 measures per mouse x 100 mice = 2100 measures. Why would you look only at the measures at one time point? Statistical analysis plan is very important. There are different approaches for . continuous outcomes (e.g. tumor volume at...