Implement the “deque” data structure. Write a program
that describes the deque and simulates its operations. You must implement all
methods given below. The program reads the sequence of commands and executes
the corresponding operation. After executing each command the program must
print one line. The possible commands for the program are:
push_front
Add (put) into the front of the deque the new element.
The program must print ok.
push_back
Add (put) a new
element to the end of the deck. The program should print ok.
pop_front
Extract the
first element from the deck. The program should print its value.
pop_back
Extract the last
item from the deck. The program should print its value.
front
Find out the
value of the first element (without deleting it). The program should print its
value.
back
Find out the
value of the last element (without deleting it). The program should print its
value.
size
Print the number
of elements in the deck.
clear
Clear the deck
(remove all elements from it) and print ok.
exit
The program
should output bye and exit.
It is guaranteed that the number of elements in the
deck at any time does not exceed 100. All operations:
·
pop_front,
·
pop_back,
·
front,
·
back
are always correct.
Input. Each line contains one command.
Output. For
each command, print the corresponding result on a separate line.
|
Sample input |
Sample output |
|
push_back 3 push_front 14 size clear push_front 1 back push_back 2 front pop_back size pop_front size exit |
ok ok 2 ok ok 1 ok 1 2 1 1 0 bye |
deque
In this problem you should
simulate the operations on the deque.
#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;
deque<int> q;
int n;
char s[100];
int main(void)
{
while (scanf("%s", s) == 1)
{
if (strcmp(s, "push_back") == 0)
{
scanf("%d", &n);
q.push_back(n);
puts("ok");
}
if (strcmp(s, "pop_back") == 0)
{
printf("%d\n", q.back());
q.pop_back();
}
if (strcmp(s, "push_front") == 0)
{
scanf("%d", &n);
q.push_front(n);
puts("ok");
}
if (strcmp(s, "pop_front") == 0)
{
printf("%d\n", q.front());
q.pop_front();
}
if (strcmp(s, "size") == 0)
{
printf("%d\n", q.size());
}
if (strcmp(s, "clear") == 0)
{
q.clear();
puts("ok");
}
if (strcmp(s, "back") == 0)
{
printf("%d\n", q.back());
}
if (strcmp(s, "front") == 0)
{
printf("%d\n", q.front());
}
if (strcmp(s, "exit") == 0)
{
puts("bye");
return 0;
}
}
return 0;
}
#include <iostream>
#include <string>
#include <deque>
using namespace std;
deque<int> q;
int n;
string s;
int main(void)
{
while (cin >> s)
{
if (s == "push_back")
{
cin >> n;
q.push_back(n);
cout << "ok" << endl;
}
if (s == "pop_back")
{
cout << q.back() << endl;
q.pop_back();
}
if (s == "push_front")
{
cin >> n;
q.push_front(n);
cout << "ok" << endl;
}
if (s == "pop_front")
{
cout << q.front() << endl;
q.pop_front();
}
if (s == "size")
{
cout << q.size() << endl;
}
if (s == "clear")
{
q.clear();
cout << "ok" << endl;
}
if (s == "back")
{
cout << q.back() << endl;
}
if (s == "front")
{
cout << q.front() << endl;
}
if (s == "exit")
{
cout << "bye" << endl;
return 0;
}
}
return 0;
}
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
Deque<Integer> q = new
LinkedList<Integer>();
while (true)
{
String s = sc.next();
if (s.equals("push_back"))
{
int x = sc.nextInt();
q.addLast(x);
System.out.println("ok");
}
if (s.equals("push_front"))
{
int x = sc.nextInt();
q.addFirst(x);
System.out.println("ok");
}
if (s.equals("pop_back"))
{
System.out.println(q.removeLast());
}
if (s.equals("pop_front"))
{
System.out.println(q.removeFirst());
}
if (s.equals("front"))
{
System.out.println(q.getFirst());
}
if (s.equals("back"))
{
System.out.println(q.getLast());
}
if (s.equals("size"))
{
System.out.println(q.size());
}
if (s.equals("clear"))
{
q.clear();
System.out.println("ok");
}
if (s.equals("exit"))
{
System.out.println("bye");
break;
}
}
sc.close();
}
}
import java.util.*;
class MyDeque
{
protected
LinkedList<Integer> v;
MyDeque()
{
v = new
LinkedList<Integer>();
}
public void push_back(int x)
{
v.addLast(x);
System.out.println("ok");
}
public void push_front(int x)
{
v.addFirst(x);
System.out.println("ok");
}
public int pop_back()
{
return v.removeLast();
}
public int pop_front()
{
return v.removeFirst();
}
public int front()
{
return v.getFirst();
}
public int back()
{
return v.getLast();
}
public int size()
{
return v.size();
}
public void clear()
{
v.clear();
System.out.println("ok");
}
public void exit()
{
System.out.println("bye");
}
}
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
MyDeque d = new MyDeque();
while(true)
{
String str = con.next();
if (str.equals("push_back"))
{
int n = con.nextInt();
d.push_back(n);
} else
if (str.equals("push_front"))
{
int n = con.nextInt();
d.push_front(n);
} else
if (str.equals("pop_back"))
{
System.out.println(d.pop_back());
} else
if (str.equals("pop_front"))
{
System.out.println(d.pop_front());
} else
if (str.equals("front"))
{
System.out.println(d.front());
} else
if (str.equals("back"))
{
System.out.println(d.back());
} else
if (str.equals("size"))
{
System.out.println(d.size());
} else
if (str.equals("clear"))
{
d.clear();
} else
{
d.exit();
break;
}
}
con.close();
}
}