ALGORITHM SERIES | Queue Composed Of Two Stacks

Jun 4, 2022 · 3 min read · algorithm English ·

Share on:

Overview

Requirements

Write a class that implements a queue with two stacks and supports the basic operations of a queue: add, poll, peek

Solving Ideas

stacks are characterized by last-in-first-out, queues are characterized by first-in-first-out
one stack as a press-in stack, the other stack as a pop-up stack, as long as the data pressed into the press-in stack and then pressed into the pop-up stack order will be restored

Golang Implementation

Note that since the data from stackPush to stackPop is only guaranteed to be coherent each time, stackPush has to press all the data into stackPop at once, and only when stackPop is empty.

 1package main
 2
 3import "fmt"
 4
 5type TwoStackQueue struct {
 6	stackPush *Stack
 7	stackPop  *Stack
 8}
 9
10func NewTwoStackQueue() *TwoStackQueue {
11	return &TwoStackQueue{
12		stackPush: NewStack(),
13		stackPop:  NewStack(),
14	}
15}
16
17func (tsq *TwoStackQueue) add(data interface{}) {
18	tsq.stackPush.Push(data)
19}
20
21func (tsq *TwoStackQueue) poll() interface{} {
22	if tsq.stackPop.Len() == 0 && tsq.stackPush.Len() == 0 {
23		fmt.Errorf("TwoStackQueue is empty")
24	} else if tsq.stackPop.Len() == 0 {
25		for tsq.stackPush.Len() != 0 {
26			tsq.stackPop.Push(tsq.stackPush.Pop())
27		}
28	}
29	value := tsq.stackPop.Pop()
30	return value
31}
32
33func (tsq *TwoStackQueue) peek() interface{} {
34	if tsq.stackPop.Len() == 0 && tsq.stackPush.Len() == 0 {
35		fmt.Errorf("TwoStackQueue is empty")
36	} else if tsq.stackPop.Len() == 0 {
37		for tsq.stackPush.Len() != 0 {
38			tsq.stackPop.Push(tsq.stackPush.Pop())
39		}
40	}
41	value := tsq.stackPop.Peek()
42	return value
43}

Test Cases

 1package main
 2
 3import (
 4	"testing"
 5
 6	"github.com/stretchr/testify/assert"
 7)
 8
 9func TestTwoStackQueue(t *testing.T) {
10	// define a getmin stack
11	tests := []struct {
12		name string
13
14		val func(tsq *TwoStackQueue)
15
16		wantRes interface{}
17	}{
18		{
19			name:    "push",
20			val:     push,
21			wantRes: 1,
22		},
23		{
24			name:    "push and poll1",
25			val:     pushpoll1,
26			wantRes: 3,
27		},
28		{
29			name:    "push and poll2",
30			val:     pushpoll2,
31			wantRes: 2,
32		},
33		{
34			name:    "push and poll3",
35			val:     pushpoll3,
36			wantRes: nil,
37		},
38	}
39	for _, tt := range tests {
40		// new TwoStackQueue
41		tsq := NewTwoStackQueue()
42		t.Run(tt.name, func(t *testing.T) {
43			tt.val(tsq)
44			res := tsq.peek()
45			assert.Equal(t, tt.wantRes, res)
46		})
47	}
48}
49
50func push(tsq *TwoStackQueue) {
51	tsq.add(1)
52	tsq.add(2)
53	tsq.add(3)
54}
55
56func pushpoll1(tsq *TwoStackQueue) {
57	tsq.add(1)
58	tsq.add(2)
59	tsq.add(3)
60	tsq.poll()
61	tsq.poll()
62}
63
64func pushpoll2(tsq *TwoStackQueue) {
65	tsq.add(1)
66	tsq.poll()
67	tsq.add(2)
68	tsq.add(3)
69}
70
71func pushpoll3(tsq *TwoStackQueue) {
72	tsq.add(1)
73	tsq.add(2)
74	tsq.poll()
75	tsq.add(3)
76	tsq.poll()
77	tsq.poll()
78}

Result:

 1$ go test -run ^TestTwoStackQueue$ . -v
 2=== RUN   TestTwoStackQueue
 3=== RUN   TestTwoStackQueue/push
 4=== RUN   TestTwoStackQueue/push_and_poll1
 5=== RUN   TestTwoStackQueue/push_and_poll2
 6=== RUN   TestTwoStackQueue/push_and_poll3
 7--- PASS: TestTwoStackQueue (0.00s)
 8    --- PASS: TestTwoStackQueue/push (0.00s)
 9    --- PASS: TestTwoStackQueue/push_and_poll1 (0.00s)
10    --- PASS: TestTwoStackQueue/push_and_poll2 (0.00s)
11    --- PASS: TestTwoStackQueue/push_and_poll3 (0.00s)
12PASS

The test scenario matches the queue's characteristics well. As you can see, a peek operation, add(1), add(2), and add(3) always return 1. In addition, you can only see 2 if you delete 1. so forth.