DS The Stack Abstract Data Type

Section 3.4 The Stack Abstract Data Type

The stack abstract data type is defined by the following structure and operations. A stack is structured, as described in Section 3.3, as an ordered collection of items where items are added to and removed from the end called the top. Stacks are ordered LIFO. The stack operations are given below.

🔗

push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
🔗

🔗
pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
🔗

🔗
peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
🔗

🔗
isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
🔗

🔗
size() returns the number of items on the stack. It needs no parameters and returns an integer.
🔗

🔗

🔗

Aside

For example, if s is a stack that has been created and starts out empty, then Table 3.4.1 shows the results of a sequence of stack operations. Under Stack Contents, the top item is listed at the far right.

🔗

Table 3.4.1. Sample Stack Operations

🔗

Stack Operation	Stack Contents	Return Value
`s.isEmpty()`	`[]`	`True`
`s.push(4)`	`[4]`
`s.push(27)`	`[4, 27]`
`s.peek()`	`[4, 27]`	`27`
`s.push(1066)`	`[4, 27, 1066]`
`s.size()`	`[4, 27, 1066]`	`3`
`s.isEmpty()`	`[4, 27, 1066]`	`false`
`s.push(4711)`	`[4, 27, 1066, 4711]`
`s.pop()`	`[4, 27, 1066]`	`4711`
`s.pop()`	`[4, 27]`	`1066`
`s.size()`	`[4, 27]`	`2`

In Kotlin, we often represent an abstract data type with an interface. An interface allows us to specify all of the functions, but we can leave out the details of their implementation. It’s a way that is built into the language that we can use to specify the operations shown above. Here’s what a Kotlin stack interface looks like:

🔗

Listing 3.4.2. Interface representing Stack ADT

🔗

interface StackADT<T> {

    // Returns true if there are no items on the stack;
    // false otherwise.
    fun isEmpty(): Boolean

    // Pushes given item on the top of the stack
    fun push(item: T)

    // Removes the item on top of the stack and returns it.
    // If the stack is empty, throws an exception.
    fun pop(): T

    // Returns the item on top of the stack without removing it.
    // If the stack is empty, throws an exception.
    fun peek(): T

    // Returns the number of items on the stack.
    fun size(): Int
}

You have attempted of activities on this page.

🔗

Prev Top Next